Introduction to Error Correction Coding
A problem encountered in data storage and communication systems is how to deal with errors which are externally introduced, either during the process of data storage and retrieval (in a data storage system) or during the process of data transmission and reception (in a data transmission system). Referring to FIG. 1, such data systems may be characterized as a transmitter communicating with a receiver over a channel, as in communication over a telephone line between two computers. The channel--or telephone line--is inherently noisy and introduces errors into the data as received by the receiver. In another example relevant to FIG. 1, the storage and retrieval of data from mass memory systems (such as computer tape drives and computer disc drives) involves a data channel comprising the interface between the storage medium (e.g. magnetic tape) and the detector (e.g. the magnetic head). Noise in the magnetic tape-magnetic head interface introduces errors into data stored and retrieved in such mass memory systems, particularly when such storage and retrieval is performed at very high data rates. In the following discussion, FIG. 1 may be thought of as depicting a transmitter modem and a receiver modem providing communication between two computers over a telephone line.
Referring to FIG. 2, the computer bytes transmitted over the channel from the transmitter modem to the receiver modem of FIG. 1 are, typically, not transmitted in a continuum but, instead are divided into blocks of bytes, each byte being transmitted, received and processed separately. In the simplified example of FIG. 2, the transmitted block consists of five three-bit bytes, while in practical application the bytes are usually 8 bits wide and the number of bytes per block may be in the tens or hundreds, or even more. However, sticking with the simplified example of FIG. 2, all five bytes of the transmitted block do not have to be dedicated to the user data, and in fact one or more of the five bytes could be reserved for other purposes, the user data being transmitted in the remaining bytes. In the example of FIG. 2, the first three bytes of the five-byte block are filled with the user data in the order received, these three bytes being the "message bytes". The remaining two bytes of the block are redundant "check bytes" and are computed from the contents of the message bytes before transmission. It is the check bytes that provide the key to the detection and removal of any errors introduced into the code block during transit through the channel. Such error correction is to be performed by the receiver of FIG. 1.